﻿#define _CRT_SECURE_NO_WARNINGS 1

//给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
//
//请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
//
//输入格式
//第一行包含整数 n 和 m。
//
//接下来 m 行每行包含三个整数 x, y, z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
//
//输出格式
//输出一个整数，表示 1 号点到 n 号点的最短距离。
//
//如果路径不存在，则输出 −1。
//
//数据范围
//1≤n≤500,
//1≤m≤105,
//图中涉及边长均不超过10000。
//
//输入样例：
//3 3
//1 2 2
//2 3 1
//1 3 4
//输出样例：
//3
//dist[n] //用于存储每个点到起点的最短距离
//st[n]   //用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
//
//每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离最短的点
//（至于为什么是这样那么这就涉及到Dijkstra算法的具体数学证明了 有兴趣的同学可以百度一下）
//
//int t = -1;       //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图
//for (int j = 1; j <= n; j++)
//{
//    if (!st[j] && (t == -1 || dist[t] > dist[j])    //该步骤即寻找还未确定最短路的点中路径最短的点
//        t = j;
//}
//通过上述操作当前我们的t代表就是剩余未确定最短路的点中 路径最短的点
//而与此同时该点的最短路径也已经确定我们将该点标记
//
//st[t] = true;
//
//然后用这个去更新其余未确定点的最短距离
//
//for (int j = 1; j <= n; j++)
//dist[j] = min(dist[j], dist[t] + g[t][j]);
////这里可能有同学要问j如果从1开始的话 会不会影响之前已经确定的点的最小距离
////但其实是不会 因为按照我们的Dijkstra算法的操作顺序 先确定最短距离的点的距离已经比后确定的要小 所以不会影响
////当然你也可以在循环判断条件里加上if(!st[i])
////这里j从1开始只是为了代码的简洁
//
//进行n次迭代后最后就可以确定每个点的最短距离
//然后再根据题意输出相应的 要求的最短距离

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 510;

int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定

int n, m;

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);     //初始化距离  0x3f代表无限大

    dist[1] = 0;  //第一个点到自身的距离为0

    for (int i = 0; i < n; i++)      //有n个点所以要进行n次 迭代
    {
        int t = -1;       //t存储当前访问的点

        for (int j = 1; j <= n; j++)   //这里的j代表的是从1号点开始
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j++)           //依次更新每个点所到相邻的点路径值
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    if (dist[n] == 0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径
    return dist[n];
}
int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);    //初始化图 因为是求最短路径
    //所以每个点初始为无限大

    while (m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);     //如果发生重边的情况则保留最短的一条边
    }

    cout << Dijkstra() << endl;
    return 0;
}